package com.bclz.scala

import scala.annotation.tailrec

 class Node[A]( ){



   self=>

   var v:A=_
   var node:Node[A]=_
   def this( v:A,node:Node[A]) {
     this()
     self.v=v
     self.node=node
   }

   def this( node:Node[A]) {
     this()
     self.node=node
   }
    def head():A=self.v
    def next():Node[A]=self.node

   /**
     * 反转链表
     * @return
     */
    def reverse(): Node[A] ={
      @tailrec
      def rescur(result:Node[A],target:Node[A]):Node[A]={
        val next = target.next()
        if(next==null)  return result
        rescur(Node(target.v,result),next)
      }
      rescur(null,self)
    }

   /**
     * 交换每两个节点位置
     * 0->1->2->3
     * 1->0->3->2
     * @return
     */
   def swapNodesInPairs(): Node[A] ={
     val pre:Node[A]=Node(self)
     var temp=pre
     while(temp.next!=null&&temp.next.next!=null){
        val start=temp.next()
        val end=temp.next().next()
        start.node=end.next()
        end.node=start
        temp.node=end
        temp=start
     }
      pre.next()
   }

   /**
     * 给定一个链表，判断链表中是否有环。
     * 常数空间复杂度O(1)(快慢指针实现)，时间复杂度
     * @return
     */
   def hasCycle():Boolean={
      if(self==null||self.next()==null) return false
      var slowNode=self.next
      var fastNode=self.next.next
      var hasCycle=true
      while (slowNode!=fastNode&&hasCycle){
          if(fastNode==null||fastNode.next==null){
            hasCycle=false
          }else{
            slowNode=slowNode.next
            fastNode=fastNode.next.next
          }
      }
      hasCycle
   }

   override def toString :String= {

     def recur(s:String,target:Node[A]):String  ={
        if(target==null) return  s
        if(s=="") recur(target.v.toString,target.next())
        else recur(s+","+target.v,target.next())
     }
     recur("",self)
   }


 }


object Node{

  def apply[A](v: A, node: Node[A]):Node[A]= new  Node[A](v,node)

  def apply[A]( node: Node[A]):Node[A]= new  Node[A](node)

  def main(args: Array[String]): Unit = {

    val value = Node(1,Node(2,Node(3,Node(4,Node(5,null)))))

    println(value.reverse())
    println(value.swapNodesInPairs())

    val n1=Node(1,null)
    val n2=Node(2,null)
    val n3=Node(3,null)
    val n4=Node(4,null)
    val n5=Node(4,null)
    val n6=Node(4,null)
    val n7=Node(4,null)
    val n8=Node(4,null)
    val n9=Node(4,null)
    n6.node=n7
    n5.node=n6
    n4.node=n5
    n3.node=n4
    n2.node=n3
    n1.node=n2
    println(n1.hasCycle())
    println(value.hasCycle())
  }

}

